This invention relates to performing QR decomposition operations in integrated circuit devices, and particularly in programmable integrated circuit devices such as programmable logic devices (PLDs).
QR decomposition (also called a QR factorization) of a matrix is a decomposition of the matrix into an orthogonal matrix Q and a right triangular matrix R. QR decomposition may be used, for example, to solve the linear least squares problem. QR decomposition also is the basis for a particular eigenvalue algorithm called the QR algorithm
One known technique for performing QR decomposition is the Gram-Schmidt technique, which calculates the Q matrix as follows (where A is the input matrix, having columns ai and elements aij):
for i=1 to n do                vi=ai         
end for                for i=1 to n do        rii=∥vi∥        qi=vi/rii         for j=i+1 to n do                    rij=qTivj             vj=vj−rijqi                         end for        
end for
As can be seen, there are two data dependencies, one in the outer loop, where qi cannot be computed until rii has been computed, and one in the inner loop, where rij cannot be computed until qTi has been computed. Such data dependencies can cause delays when the computation is performed in hardware, and also may be of concern in a software implementation in a multicore processor environment, or even in a single core processor environment if the processor is deeply pipelined and the pipeline is optimized for more functions more common than division.